
\begin{QUOTE}{}{}
想体验把暴搜改改就是正解的快感吗? 想体验状压 dp 看似状态多到爆炸实际一跑却嗷嗷快 (实际有效的状态数很少) 的荣耀吗? 记忆化搜索, 符合您的需求! 只要 998 , 记忆化搜索带回家! 记忆化搜索, 记忆化搜索, 再说一遍, 记忆化搜索!
\end{QUOTE}

\hr

\subsection{记忆化搜索是啥}

好，就以 \href{https://www.luogu.org/problemnew/show/P1048}{洛谷 P1048 采药} 为例，我不会动态规划，只会搜索，我就会直接写一个粗暴的  DFS  :

\begin{itemize}
\item 注: 为了方便食用, 本文中所有代码省略头文件
\end{itemize}

\begin{cppcode}
int n, t;
int tcost[103], mget[103];
int ans = 0;
void dfs(int pos, int tleft, int tans) {
  if (tleft < 0) return;
  if (pos == n + 1) {
    ans = max(ans, tans);
    return;
  }
  dfs(pos + 1, tleft, tans);
  dfs(pos + 1, tleft - tcost[pos], tans + mget[pos]);
}
int main() {
  cin >> t >> n;
  for (int i = 1; i <= n; i++) cin >> tcost[i] >> mget[i];
  dfs(1, t, 0);
  cout << ans << endl;
  return 0;
}
\end{cppcode}

这就是个十分智障的大暴搜是吧 ......

emmmmmm....... $30$ 分

然后我心血来潮, 想不借助任何 "外部变量"(就是 dfs 函数外且 \textbf{ 值随 dfs 运行而改变的变量 }), 比如 ans

把 ans 删了之后就有一个问题: 我们拿什么来记录答案?

答案很简单:

\textbf{返回值!}

此时 $dfs(pos,tleft)$ 返回在时间 $tleft$ 内采集 \textbf{ 后 }$pos$ 个草药, 能获得的最大收益

不理解就看看代码吧:

\begin{cppcode}
int n, time;
int tcost[103], mget[103];
int dfs(int pos, int tleft) {
  if (pos == n + 1) return 0;
  int dfs1, dfs2 = -INF;
  dfs1 = dfs(pos + 1, tleft);
  if (tleft >= tcost[pos]) dfs2 = dfs(pos + 1, tleft - tcost[pos]) + mget[pos];
  return max(dfs1, dfs2);
}
int main() {
  cin >> time >> n;
  for (int i = 1; i <= n; i++) cin >> tcost[i] >> mget[i];
  cout << dfs(1, time) << endl;
  return 0;
}
\end{cppcode}

\sout{emmmmmm....... 还是 ${30}$ 分}

但这个时候, 我们的程序已经不依赖任何外部变量了.

然后我非常无聊, 将所有 dfs 的返回值都记录下来, 竟然发现......

\textbf{震惊, 对于相同的 pos 和 tleft,dfs 的返回值总是相同的!}

想一想也不奇怪, 因为我们的 dfs 没有依赖任何外部变量.

旁白: 像 $tcost[103]$,$mget[103]$ 这种东西不算是外部变量, 因为她们在 dfs 过程中不变.

然后?

开个数组 $mem$ , 记录下来每个 $dfs(pos,tleft)$ 的返回值. 刚开始把 $mem$ 中每个值都设成 $-1$ (代表没访问过). 每次刚刚进入一个 dfs 前 (我们的 dfs 是递归调用的嘛), 都检测 $mem[pos][tleft]$ 是否为 $-1$ , 如果是就正常执行并把答案记录到 $mem$ 中, 否则?

\textbf{直接返回 $mem$ 中的值!}

\begin{cppcode}
int n, t;
int tcost[103], mget[103];
int mem[103][1003];
int dfs(int pos, int tleft) {
  if (mem[pos][tleft] != -1) return mem[pos][tleft];
  if (pos == n + 1) return mem[pos][tleft] = 0;
  int dfs1, dfs2 = -INF;
  dfs1 = dfs(pos + 1, tleft);
  if (tleft >= tcost[pos]) dfs2 = dfs(pos + 1, tleft - tcost[pos]) + mget[pos];
  return mem[pos][tleft] = max(dfs1, dfs2);
}
int main() {
  memset(mem, -1, sizeof(mem));
  cin >> t >> n;
  for (int i = 1; i <= n; i++) cin >> tcost[i] >> mget[i];
  cout << dfs(1, t) << endl;
  return 0;
}
\end{cppcode}

此时 $mem$ 的意义与 dfs 相同:

\begin{QUOTE}{}{}
在时间 $tleft$ 内采集 \textbf{ 后 } $pos$ 个草药, 能获得的最大收益
\end{QUOTE}

这能 ac ?

能.\textbf{这就是 "采药" 那题的 AC 代码}

好我们 yy 出了记忆化搜索

\paragraph{总结一下记忆化搜索是啥}

\begin{itemize}
\item 不依赖任何 \textbf{外部变量}
\item 答案以返回值的形式存在, 而不能以参数的形式存在 (就是不能将 dfs 定义成 $dfs(pos ,tleft , nowans )$, 这里面的 nowans 不符合要求).
\item 对于相同一组参数, dfs 返回值总是相同的
\end{itemize}

\hr

\subsection{记忆化搜索与动态规划的关系}

有人会问: 记忆化搜索难道不是搜索?

是搜索. 但个人认为她更像 dp :

不信你看 $mem$ 的意义:

\begin{QUOTE}{}{}
在时间 $tleft$ 内采集 \textbf{ 后 } $pos$ 个草药, 能获得的最大收益
\end{QUOTE}

这不就是 dp 的状态?

由上面的代码中可以看出:

\begin{QUOTE}{}{}
$mem[pos][tleft] = max(mem[pos+1][tleft-tcost[pos]]+mget[pos]\ ,\ mem[pos+1][tleft])$
\end{QUOTE}

这不就是 dp 的状态转移?

个人认为:

\begin{QUOTE}{}{}
记忆化搜索约等于动态规划,\textbf{(印象中) 任何一个 dp 方程都能转为记忆化搜索 }
\end{QUOTE}

大部分记忆化搜索的状态 / 转移方程与 dp 都一样, 时间复杂度 / 空间复杂度与 \textbf{ 不加优化的 } dp 完全相同

比如:

$dp[i][j][k] = dp[i+1][j+1][k-a[j]] + dp[i+1][j][k]$

转为

\begin{cppcode}
int dfs(int i, int j, int k) {
  边界条件
  if (mem[i][j][k] != -1) return mem[i][j][k];
  return mem[i][j][k] = dfs(i + 1, j + 1, k - a[j]) + dfs(i + 1, j, k);
}
int main() {
  memset(mem, -1, sizeof(mem));
  读入
  cout << dfs(1, 0, 0) << endl;
}
\end{cppcode}

\hr

\subsection{如何写记忆化搜索}

\subsubsection{方法 I}

\begin{enumerate}
\item 把这道题的 dp 状态和方程写出来
\item 根据他们写出 dfs 函数
\item 添加记忆化数组
\end{enumerate}

举例:

$dp[i] = max\{dp[j]+1\}\quad 1 \leq j < i \text{且}a[j]<a[i]$  (最长上升子序列)

转为

\begin{cppcode}
int dfs(int i) {
  if (mem[i] != -1) return mem[i];
  int ret = 1;
  for (int j = 1; j < i; j++)
    if (a[j] < a[i]) ret = max(ret, dfs(j) + 1);
  return mem[i] = ret;
}
int main() {
  memset(mem, -1, sizeof(mem));
  读入
  cout << dfs(n) << endl;
}
\end{cppcode}

\subsubsection{方法 II}

\begin{enumerate}
\item 写出这道题的暴搜程序 (最好是  dfs  )
\item 将这个 dfs 改成 "无需外部变量" 的 dfs
\item 添加记忆化数组
\end{enumerate}

举例: 本文最开始介绍 "什么是记忆化搜索" 时举的 "采药" 那题的例子

\hr

\subsection{记忆化搜索的优缺点}

优点:

\begin{itemize}
\item 记忆化搜索可以避免搜到无用状态, 特别是在有状态压缩时
\end{itemize}

举例: 给你一个有向图 (注意不是完全图), 经过每条边都有花费, 求从点 1 出发, 经过每个点 \textbf{ 恰好一次 } 后的最小花费 (最后不用回到起点), 保证路径存在.

dp 状态很显然:

设 $dp[pos][mask]$ 表示身处在 $pos$ 处, 走过 $mask$ (mask 为一个二进制数) 中的顶点后的最小花费

常规 $dp$ 的状态为 $O(n\cdot 2^n)$ , 转移复杂度 (所有的加在一起) 为 $O(m)$

但是! 如果我们用记忆化搜索, 就可以避免到很多无用的状态, 比如 $pos$ 为起点却已经经过了 $>1$ 个点的情况.

\begin{itemize}
\item 不需要注意转移顺序 (这里的 "转移顺序" 指正常 dp 中 for 循环的嵌套顺序以及循环变量是递增还是递减)
\end{itemize}

举例: 用常规 dp 写 "合并石子" 需要先枚举区间长度然后枚举起点, 但记忆化搜索直接枚举断点 (就是枚举当前区间由哪两个区间合并而成) 然后递归下去就行

\begin{itemize}
\item 边界情况非常好处理, 且能有效防止数组访问越界
\item 有些 dp (如区间 dp) 用记忆化搜索写很简单但正常 dp 很难
\item 记忆化搜索天生携带搜索天赋, 可以使用技能 "剪枝"!
\end{itemize}

缺点:

\begin{itemize}
\item 致命伤: 不能滚动数组!
\item 有些优化比较难加
\item 由于递归, 有时效率较低但不至于 TLE (状压 dp 除外)
\end{itemize}

\hr

\subsection{记忆化搜索的注意事项}

\begin{itemize}
\item 千万别忘了加记忆化! (别笑, 认真的
\item 边界条件要加在检查当前数组值是否为非法数值 (防止越界)
\item 数组不要开小了 (逃
\end{itemize}

\subsection{模板}

\begin{cppcode}
int g[MAXN] ； int f(传入数值) {
  if (g[规模] != 无效数值) return g[规模];
  if (终止条件) return 最小子问题解;
  g[规模] = f(缩小规模);
  return g[规模];
}
int main() {
  ... memset(g, 无效数值, sizeof(g));
  ...
}
\end{cppcode}
